package com.ycy.leetcode.tree;

import java.util.LinkedList;
import java.util.List;

public class TreePreCommonPrefix {


  public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }

  }


 // 二叉树 最近公共祖先
  public static void main(String[] args) {
    TreeNode root;
       /*
         500
    250      1000
  150 350  750 1250
           /
         650
     */
    root = new TreeNode(500);
    root.left = new TreeNode(250);
    root.right = new TreeNode(1000);

    root.left.left = new TreeNode(150);
    root.left.right = new TreeNode(350);

    root.right.left = new TreeNode(750);
    root.right.right = new TreeNode(1250);

    root.right.left.left = new TreeNode(650);
    TreePreCommonPrefix solution = new TreePreCommonPrefix();
    TreeNode treeNode = solution.lowestCommonAncestor(root, new TreeNode(750), new TreeNode(650));
    System.out.println(treeNode.val);

  }


  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> ppath = getPath(root, p);
    List<TreeNode> qpath = getPath(root, q);

    int i = 0;
    TreeNode target = null;
    //同时遍历 两个路径，最后一次相同节点就是最近公共祖先
    while (i < ppath.size() && i < qpath.size()) {
      if (ppath.get(i).val == qpath.get(i).val) {
        target = ppath.get(i);
      } else {
        break;
      }
      i ++;
    }

    return target;
  }


  public List<TreeNode> getPath(TreeNode root, TreeNode target) {
    List<TreeNode> path = new LinkedList<TreeNode>();
    preOrder(root, path, target);
    //for(TreeNode tr:path){
    //    System.out.println(tr.val);
    //}
    return path;
  }

  public boolean preOrder(TreeNode root, List<TreeNode> path, TreeNode target) {

    if (root == null) {
      return false;
    }

    path.add(root);

    // 查询到该节点可以直接返回
    if (root.val == target.val) {
      return true;
    }

    boolean findLeft = preOrder(root.left, path, target);
    if (findLeft) return true;
    boolean findRight = preOrder(root.right, path, target);
    if (findRight) return true;

    path.remove(path.size() - 1);
    return false;
  }


}
